package ljl.alg.jianzhioffer.round2;

import java.util.HashMap;
import java.util.Map;

/**
 * 怎么感觉又把我卡住了
 * 一瞬间，没有思路！
 * */
public class _35_copy_random_list {
    
    class Node {
        int val;
        Node next;
        Node random;
        
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    
    /**
     * 先别玩花的，先 hashmap 安排起来
     * 我想是不是搞两个 map，一个把 node 和 random 连起来
     * 一个把旧 node 和新 node 连起来
     *
     * 自己写出来了。
     * 意思就是没学到东西
     *
     * */
    public Node copyRandomList886(Node head) {
        if (head == null) return null;
    
        Map<Node, Node> toRandom = new HashMap<>();
        Map<Node, Node> toNew = new HashMap<>();
    
        // 这个循环干了三件事
        // 1. 新旧 node 连起来
        // 2. random 连起来
        Node dummy = new Node(1);
        Node p = head;
        Node q = dummy;
        while (p != null) {
            Node newNode = new Node(p.val);
            
            toNew.put(p, newNode);
            toRandom.put(p, p.random);
            
            q.next = newNode;
            p = p.next;
            q = q.next;
        }
        
        // 1. 根据旧的找新的
        // 2. 根据旧的找 random，random 也是个旧的
        // 3. 根据旧 random 再找到新节点，连接 1 的新和这个新的
        p = head;
        while (p != null) {
            Node newNode = toNew.get(p);
            Node oldRandom = toRandom.get(p);
            newNode.random = toNew.get(oldRandom);
            p = p.next;
        }
        
        return dummy.next;
    }
    
    /**
     * 我的办法又有些笨逼，还是有进步空间的
     *
     * 看完这个，感觉我的解法太傻屄了
     *
     * */
    public Node copyRandomList2(Node head) {
        if (head == null) return null;
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        
        cur = head;
        while (cur != null) {
            Node newNode = map.get(cur);
            
            newNode.next = map.get(cur.next);
            newNode.random = map.get(cur.random);
            
            cur = cur.next;
        }
        return map.get(head);
    }
    
    /**
     * 我都没思考直接看答案了
     * 还是应该想想！
     * 不然成背古诗了
     *
     * 省了空间，但是不提倡，太繁琐
     * */
    public Node copyRandomList(Node head) {
        
        if (head == null) return null;
    
        Node p = head;
        // 每个节点后面都复制一个
        while (p != null) {
            Node newNode = new Node(p.val);
            newNode.next = p.next;
            p.next = newNode;
            p = newNode.next;
        }
        
        p = head;
        // 把 random 连接
        while (p != null) {
            if (p.random != null) {
                p.next.random = p.random.next;
            }
            // 傻逼写法。为什么可以 p.next.next？因为 p 不是 null 则 p.next 必定也不是 null！
//            p = p.next;
//            if (p != null)
//                p = p.next;
            p = p.next.next;
        }
        
        // 把链表拆开
        Node newHead = head.next;
        Node pre = head, cur = newHead;
        // pre cur xx xx
        while (cur != null) {
            // 这个顺序是不能换的，虽然他俩好像毫无关联，但是其实是有关联的
            // 要 pre 往后走两个格子，cur 再走
            // 不然如果 cur 先走，pre 就迷路了
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            
            pre = pre.next;
            cur = cur.next;
        }
        
        // 恢复原始链表最后一个节点
        // 不恢复也没事！
        // 试了试，不恢复会被发现，还是得恢复
        pre.next = null;
        
        return newHead;
    }
}
